package 剑指offer;

public class A3 {
    // //使用位运算
    // public int[] countBits(int n) {
    //     int[] res=new int[n+1];
    //     res[0]=0;
    //     if (n==0) {
    //         return res;
    //     }
    //     res[1]=1;
    //     for (int i = 2; i <=n; i++) {
    //         int middle=i;
    //         int middle1=middle-1;
    //         res[middle]=res[middle&middle1]+1;
    //     }
    //     return res;
    // }

    //递归，方法一的逆向思路
    public int[] countBits(int n) {
        int[] res=new int[n+1];
        res[0]=0;
        if (n==0) {
            return res;
        }
        for (int i = 1; i < n+1; i++) {
            if (res[i]==0) {
                res[i]=res[i-1]+1;
            }
            int middle=i<<1;
            while (middle<=n) {
                res[middle]=res[i];
                middle<<=1;
            }
        }
        return res;
    }
}
